public class BinarySearchTree<T extends Comparable<T>> {
    static class Node<T> {
        public T val;
        public Node<T> left;
        public Node<T> right;
        public Node(T val) {
            this.val = val;
        }
    }
    public Node<T> root;

    //查询
    public T get(T val) {
        Node<T> cur = root;
        while(cur != null) {
            if(cur.val.compareTo(val) < 0) {
                cur = cur.right;
            }else if(cur.val.compareTo(val) > 0) {
                cur = cur.left;
            }else{
                return cur.val;
            }
        }
        return null;
    }

    //插入
    public boolean add(T val) {
        if(root == null) {
            root = new Node<>(val);
            return true;
        }
        Node<T> prev = root;
        Node<T> cur = root;
        while(cur != null) {
            prev = cur;
            if(cur.val.compareTo(val) < 0) {
                cur = cur.right;
            }else if(cur.val.compareTo(val) > 0) {
                cur = cur.left;
            }else{
                return false;
            }
        }
        if(prev.val.compareTo(val) > 0) {
            prev.left = new Node<>(val);
        }else{
            prev.right = new Node<>(val);
        }
        return true;
    }
    //删除
    public boolean remove(T val) {
        Node<T> prev = root;
        Node<T> aim = root;
        //寻找目标节点和其父节点
        while(aim != null) {
            if(aim.val.compareTo(val) < 0) {
                prev = aim;
                aim = aim.right;
            }else if(aim.val.compareTo(val) > 0) {
                prev = aim;
                aim = aim.left;
            }else{
                break;
            }
        }
        if(aim == null) {
            return false;
        }
        if(aim.left == null) {
            if(aim == root) {
                root = aim.right;
            }else if(aim == prev.left){
                prev.left = aim.right;
            }else{
                prev.right = aim.right;
            }
        }else if(aim.right == null){
            if(aim == root) {
                root = aim.left;
            }else if(aim == prev.left){
                prev.left = aim.left;
            }else{
                prev.right = aim.left;
            }
        }else {
            //从目标节点开始找到左分支中的最大节点
            Node<T> prev2 = aim;
            Node<T> cur = aim.left;
            while(cur.right != null) {
                prev2 = cur;
                cur = cur.right;
            }
            aim.val = cur.val;
            if(prev2 == aim) {
                prev2.left = cur.left;
            }else{
                prev2.right = cur.left;
            }
        }
        return true;
    }
}
